复杂链表的复制

Posted on | In | | reads times

复杂链表的复制

  • 先复制链表，通过map保存对应的新链表节点和原链表节点，然后复制random链表指针。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    function RandomListNode(x){
        this.label = x;
        this.next = null;
        this.random = null;
    }
    function Clone(pHead)
    {
        // write code here
        if(pHead==null)return null;
        const m=new Map();
        let p=pHead;
        let p2=new RandomListNode(pHead.label);
        const pHead2=p2;
        map.set(p,p2)
        while(p){
            if(p.next)p2.next=new RandomListNode(p.next.label);
            else p2.next=null;
            p=p.next;
            p2=p2.next;
            m.set(p,p2)
        }
        p=pHead;
        p2=pHead2;
        while(p!==null){
            p2.random=m.get(p.random);
            p=p.next;
            p2=p2.next;
        }
        return pHead2;
    }